#include <cmath>
#include <fstream>
#include <sstream>
#include "pathFinding.h"

static const int allow = 0;
static const int forbid = 1;
static const int weighl = 10000;
static const int weighh = 14142;
static const vector<Pos> directs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {-1, 1}, {1, -1}, {-1, -1}};
static const vector<DirectWeigh> directWeighs = {
    {0, 1, weighl}, {0, -1, weighl}, {1, 0, weighl}, {-1, 0, weighl}, {1, 1, weighh}, {-1, 1, weighh}, {1, -1, weighh}, {-1, -1, weighh}};

inline int PathFinding::evaluateCost(Pos s, Pos e)
{
    double dis = pow((s.x_ - e.x_), 2) + pow((s.y_ - e.y_), 2);
    dis = sqrt(dis);
    return dis * weighl;
}

inline bool PathFinding::sideCheck(int x, int y)
{
    if (x < 0 || x >= mapLength() || y < 0 || y >= mapWidth())
        return false;
    return true;
}

inline bool PathFinding::walkAble(int x, int y)
{
    if (x < 0 || x >= mapLength() || y < 0 || y >= mapWidth())
        return false;
    if (this->mapInfo_[x][y])
        return false;
    return true;
}

inline void PathFinding::initMapByLengthAndWidth(int mapLength, int mapWidth)
{
    mapInfo_ = vector<vector<int>>(mapLength, vector<int>(mapWidth, 0));
}

inline void PathFinding::setMapBlock(int x, int y, int blockType)
{
    if (sideCheck(x, y))
        mapInfo_[x][y] = blockType;
}

void PathFinding::initMapByFile(const string &fileName)
{
    mapInfo_ = {};
    ifstream f(fileName);
    int n;
    string line;
    while (getline(f, line))
    {
        vector<int> vl;
        istringstream iss(line);
        while (iss >> n)
            vl.push_back(n);
        mapInfo_.push_back(vl);
    }
    f.close();
}

void PathFinding::astar(Pos start, Pos end, vector<Pos> &result)
{
    if (!walkAble(start.x_, start.y_) || !walkAble(end.x_, end.y_))
        return;
    vector<vector<int>> closeList(mapLength(), vector<int>(mapWidth(), 0));
    vector<vector<Pre>> pres(mapLength(), vector<Pre>(mapWidth()));

    priority_queue<State> openList;
    State s{start.x_, start.y_, 0, evaluateCost(start, end)};
    openList.push(s);
    while (!openList.empty())
    {
        State t = openList.top();
        openList.pop();
        closeList[t.x_][t.y_] = 1;
        for (int i = 0; i < directWeighs.size(); ++i)
        {
            DirectWeigh d = directWeighs[i];
            Pos p{t.x_ + d.x_, t.y_ + d.y_};
            if (!walkAble(p.x_, p.y_))
                continue;
            if (closeList[p.x_][p.y_])
                continue;
            int cost = t.cost_ + d.weigh_;
            int weigh = cost + evaluateCost(p, end);
            State t1{p.x_, p.y_, cost, weigh};
            Pre &pre = pres[p.x_][p.y_];
            if (pre.cost_ > t1.cost_)
            {
                pre.x_ = t.x_;
                pre.y_ = t.y_;
                pre.cost_ = t1.cost_;
                openList.push(t1);
            }

            if (t1.x_ == end.x_ && t1.y_ == end.y_)
            {
                result.push_back(end);
                Pos p{end.x_, end.y_};
                while (-1 != pres[p.x_][p.y_].x_)
                {
                    Pre &pre = pres[p.x_][p.y_];
                    p.x_ = pre.x_;
                    p.y_ = pre.y_;
                    result.push_back(p);
                }
                return;
            }
        }
    }
}

bool PathFinding::forceNeighbor(State start, Pos end, Pos direct, priority_queue<State> &openList, vector<vector<Pre>> &pres)
{
    bool b = false;

    int x1 = start.x_ + direct.y_;
    int y1 = start.y_ + direct.x_;
    int x11 = x1 + direct.x_;
    int y11 = y1 + direct.y_;
    if (this->sideCheck(x1, y1) && this->sideCheck(x11, y11))
    {
        if (this->mapInfo_[x1][y1] && !this->mapInfo_[x11][y11])
        {
            b = b || true;
            int cost = start.cost_ + weighh;
            int weigh = cost + this->evaluateCost({x11, y11}, end);
            State s{x11, y11, cost, weigh, direct.x_ + direct.y_, direct.y_ + direct.x_};
            Pre &pre = pres[s.x_][s.y_];
            if (pre.cost_ > cost)
            {
                openList.push(s);
                pre.x_ = start.x_;
                pre.y_ = start.y_;
                pre.cost_ = cost;
            }
        }
    }

    int x2 = start.x_ - direct.y_;
    int y2 = start.y_ - direct.x_;
    int x21 = x2 + direct.x_;
    int y21 = y2 + direct.y_;
    if (this->sideCheck(x2, y2) && this->sideCheck(x21, y21))
    {
        if (this->mapInfo_[x2][y2] && !this->mapInfo_[x21][y21])
        {
            b = b || true;
            int cost = start.cost_ + weighh;
            int weigh = cost + this->evaluateCost({x21, y21}, end);
            State s{x21, y21, cost, weigh, direct.x_ - direct.y_, direct.y_ - direct.x_};
            Pre &pre = pres[s.x_][s.y_];
            if (pre.cost_ > cost)
            {
                openList.push(s);
                pre.x_ = start.x_;
                pre.y_ = start.y_;
                pre.cost_ = cost;
            }
        }
    }
    return b;
}

bool PathFinding::jumpPoint(State start, Pos end, Pos direct, priority_queue<State> &openList, vector<vector<Pre>> &pres)
{
    State s = start;
    s.directX_ = direct.x_;
    s.directY_ = direct.y_;
    while (1)
    {
        if (!direct.x_ || !direct.y_)
        {
            s.x_ += direct.x_;
            s.y_ += direct.y_;
            s.cost_ += weighl;
            if (!this->walkAble(s.x_, s.y_))
                return false;
            if (s.x_ == end.x_ && s.y_ == end.y_ || this->forceNeighbor(s, end, direct, openList, pres))
            {
                if (s.x_ == end.x_ && s.y_ == end.y_)
                {
                    s.weigh_ = 0;
                }
                else
                {
                    s.weigh_ = s.cost_ + this->evaluateCost({s.x_, s.y_}, end);
                }
                Pre &pre = pres[s.x_][s.y_];
                if (pre.cost_ > s.cost_)
                {
                    openList.push(s);
                    pre.x_ = start.x_;
                    pre.y_ = start.y_;
                    pre.cost_ = s.cost_;
                    return true;
                }
            }
        }
        else
        {
            bool b = false;
            b = this->forceNeighbor(s, end, {direct.x_, 0}, openList, pres) || b;
            b = this->forceNeighbor(s, end, {0, direct.y_}, openList, pres) || b;
            if (b)
            {
                Pre &pre = pres[s.x_][s.y_];
                if (s.x_ != start.x_ && s.y_ != start.y_ && pre.cost_ > s.cost_)
                {
                    pre.x_ = start.x_;
                    pre.y_ = start.y_;
                    pre.cost_ = s.cost_;
                }
                int x = s.x_;
                int y = s.y_;
                int dx = direct.x_;
                int dy = direct.y_;
                bool b1 = this->sideCheck(x + dx, y) && mapInfo_[x + dx][y];
                bool b2 = this->sideCheck(x, y + dy) && mapInfo_[x][y + dy];
                bool b3 = this->sideCheck(x + dx, y + dy) && !mapInfo_[x + dx][y + dy];
                if ((b1 || b2) && b3)
                    return true;
            }

            s.x_ += direct.x_;
            s.y_ += direct.y_;
            s.cost_ += weighh;
            if (!this->walkAble(s.x_, s.y_))
                return false;
            if (s.x_ == end.x_ && s.y_ == end.y_)
            {
                s.weigh_ = 0;
                Pre &pre = pres[s.x_][s.y_];
                if (pre.cost_ > s.cost_)
                {
                    openList.push(s);
                    pre.x_ = start.x_;
                    pre.y_ = start.y_;
                    pre.cost_ = s.cost_;
                    return true;
                }
            }
            bool r = false;
            r = this->jumpPoint(s, end, {direct.x_, 0}, openList, pres) || r;
            r = this->jumpPoint(s, end, {0, direct.y_}, openList, pres) || r;
            if (r)
            {
                Pre &pre = pres[s.x_][s.y_];
                if (pre.cost_ > s.cost_)
                {
                    pre.x_ = start.x_;
                    pre.y_ = start.y_;
                    pre.cost_ = s.cost_;

                    s.x_ += direct.x_;
                    s.y_ += direct.y_;
                    s.cost_ += weighh;
                    s.weigh_ = s.cost_ + evaluateCost({s.x_, s.y_}, end);
                    Pre &ppre = pres[s.x_][s.y_];
                    if (walkAble(s.x_, s.y_) && ppre.cost_ > s.cost_)
                    {
                        openList.push(s);
                        ppre.x_ = start.x_;
                        ppre.y_ = start.y_;
                        ppre.cost_ = s.cost_;
                    }
                    return true;
                }
            }
        }
    }
}

void PathFinding::jps(Pos start, Pos end, vector<Pos> &result)
{
    if (!walkAble(start.x_, start.y_) || !walkAble(end.x_, end.y_))
        return;

    priority_queue<State> openList;
    int weigh = this->evaluateCost(start, end);
    State stateS{start.x_, start.y_, 0, weigh, 0, 0};
    vector<vector<Pre>> pres(mapLength(), vector<Pre>(mapWidth()));
    openList.push(stateS);

    while (!openList.empty())
    {
        State t = openList.top();
        openList.pop();
        if (t.x_ == end.x_ && t.y_ == end.y_)
        {
            result.push_back(end);
            Pos p(end.x_, end.y_);
            while (-1 != pres[p.x_][p.y_].x_)
            {
                Pre &pre = pres[p.x_][p.y_];
                p.x_ = pre.x_;
                p.y_ = pre.y_;
                result.push_back(p);
            }
            return;
        }

        int directX = t.directX_;
        int directY = t.directY_;
        vector<Pos> dps;
        if (!directX && !directY)
        {
            dps = directs;
        }
        else if (directX && directY)
        {
            dps.push_back({directX, 0});
            dps.push_back({0, directY});
            dps.push_back({directX, directY});
        }
        else
        {
            dps.push_back({directX, directY});
        }
        for (int i = 0; i < dps.size(); ++i)
        {
            this->jumpPoint(t, end, dps[i], openList, pres);
        }
    }
}

//-------------------------js cpp binding-----------------------
Nan::Persistent<v8::Function> PathFinding::constructor;

NAN_MODULE_INIT(PathFinding::Init)
{
    v8::Local<v8::FunctionTemplate> tpl = Nan::New<v8::FunctionTemplate>(New);
    tpl->SetClassName(Nan::New("pathFinding").ToLocalChecked());
    tpl->InstanceTemplate()->SetInternalFieldCount(1);

    Nan::SetPrototypeMethod(tpl, "mapLength", MAPLENGTH);
    Nan::SetPrototypeMethod(tpl, "mapWidth", MAPWIDTH);
    Nan::SetPrototypeMethod(tpl, "initMapByLengthAndWidth", INITMAPBYLENGTHANDWIDTH);
    Nan::SetPrototypeMethod(tpl, "setMapBlock", SETMAPBLOCK);
    Nan::SetPrototypeMethod(tpl, "initMapByFile", INITMAPBYFILE);
    Nan::SetPrototypeMethod(tpl, "astar", ASTAR);
    Nan::SetPrototypeMethod(tpl, "jps", JPS);

    constructor.Reset(Nan::GetFunction(tpl).ToLocalChecked());
    Nan::Set(target, Nan::New("pathFinding").ToLocalChecked(), Nan::GetFunction(tpl).ToLocalChecked());
}
NAN_METHOD(PathFinding::New)
{
    if (info.IsConstructCall())
    {
        PathFinding *p = new PathFinding();
        p->Wrap(info.This());
        info.GetReturnValue().Set(info.This());
    }
    else
    {
        const int argc = 1;
        v8::Local<v8::Value> argv[argc] = {info[0]};
        v8::Local<v8::Function> cons = Nan::New(constructor);
        info.GetReturnValue().Set(Nan::NewInstance(cons, argc, argv).ToLocalChecked());
    }
}

NAN_METHOD(PathFinding::MAPLENGTH)
{
    PathFinding *p = Nan::ObjectWrap::Unwrap<PathFinding>(info.This());
    int mapLength = p->mapLength();
    info.GetReturnValue().Set(mapLength);
}
NAN_METHOD(PathFinding::MAPWIDTH)
{
    PathFinding *p = Nan::ObjectWrap::Unwrap<PathFinding>(info.This());
    int mapWidth = p->mapWidth();
    info.GetReturnValue().Set(mapWidth);
}
NAN_METHOD(PathFinding::INITMAPBYLENGTHANDWIDTH)
{
    PathFinding *p = Nan::ObjectWrap::Unwrap<PathFinding>(info.This());
    int mapLength = info[0]->IntegerValue();
    int mapWidth = info[1]->IntegerValue();
    p->initMapByLengthAndWidth(mapLength, mapWidth);
    info.GetReturnValue().Set(1);
}
NAN_METHOD(PathFinding::SETMAPBLOCK)
{
    PathFinding *p = Nan::ObjectWrap::Unwrap<PathFinding>(info.This());
    int x = info[0]->IntegerValue();
    int y = info[1]->IntegerValue();
    int blockType = info[2]->IntegerValue();
    p->setMapBlock(x, y, blockType);
    info.GetReturnValue().Set(1);
}
NAN_METHOD(PathFinding::INITMAPBYFILE)
{
    PathFinding *p = Nan::ObjectWrap::Unwrap<PathFinding>(info.This());
    v8::String::Utf8Value fName(info[0]->ToString());
    std::string fileName = std::string(*fName);
    p->initMapByFile(fileName);
    info.GetReturnValue().Set(1);
}
NAN_METHOD(PathFinding::ASTAR)
{
    PathFinding *p = Nan::ObjectWrap::Unwrap<PathFinding>(info.This());
    int startX = info[0]->IntegerValue();
    int startY = info[1]->IntegerValue();
    int endX = info[2]->IntegerValue();
    int endY = info[3]->IntegerValue();
    vector<Pos> result;
    Pos startPos(startX, startY);
    Pos endPos(endX, endY);
    p->astar(startPos, endPos, result);
    v8::Local<v8::Array> arr = Nan::New<v8::Array>(result.size() * 2);
    int i = 0;
    for (int j = result.size() - 1; j >= 0; --j)
    {
        Nan::Set(arr, i++, Nan::New(result[j].x_));
        Nan::Set(arr, i++, Nan::New(result[j].y_));
    }
    info.GetReturnValue().Set(arr);
}
NAN_METHOD(PathFinding::JPS)
{
    PathFinding *p = Nan::ObjectWrap::Unwrap<PathFinding>(info.This());
    int startX = info[0]->IntegerValue();
    int startY = info[1]->IntegerValue();
    int endX = info[2]->IntegerValue();
    int endY = info[3]->IntegerValue();
    vector<Pos> result;
    Pos startPos(startX, startY);
    Pos endPos(endX, endY);
    p->jps(startPos, endPos, result);
    v8::Local<v8::Array> arr = Nan::New<v8::Array>(result.size() * 2);
    int i = 0;
    for (int j = result.size() - 1; j >= 0; --j)
    {
        Nan::Set(arr, i++, Nan::New(result[j].x_));
        Nan::Set(arr, i++, Nan::New(result[j].y_));
    }
    info.GetReturnValue().Set(arr);
}